package com.sort;

/**
 * Created by Lxk on 2019/5/21.
 */
public class Merge {

    private static void merge(int[] arr,int lo,int hi,int mid){
        int[] temp = new int[arr.length];
        for(int i = lo;i <= hi; i++){
            temp[i] = arr[i];
        }

        int i = lo,j = mid+1;
        for(int k = lo; k <= hi; k++){
            if(i>mid){
                arr[k] = temp[j++];
            }else if(j>hi){
                arr[k] = temp[i++];
            }else if(temp[i] < temp[j]){
                arr[k] = temp[i++];
            }else{
                arr[k] = temp[j++];
            }
        }

    }

    public static void mergeSort(int[] arr,int lo,int hi){
        if(lo >= hi){
            return ;
        }
        int mid = (lo+hi)/2;
        mergeSort(arr,lo,mid);
        mergeSort(arr,mid,hi);
        merge(arr,lo,hi,mid);
    }

}
